1. Technical Field
The present invention relates to a method of and apparatus for reviewing work items for allocation to a resource, particularly but not exclusively suited to a work allocation system.
2. Related Art
Work allocation systems are well known and are generally referred to as scheduling systems, resource allocation systems, or workflow systems. Essentially, work allocation systems are concerned with optimising the allocation of a plurality of resources to a plurality of tasks given certain constraints.
In many known systems, work allocation is modelled using so-called agent-based technology. An agent is a computer program that acts on behalf of an entity such as a user or a piece of equipment. The agent typically holds data relating to the entity that it represents and is provided with decision-making software for making decisions on behalf of the entity. In the context of work allocation systems, an agent is known to represent single entities such as a resource, a work-processing centre, and a central administration centre.
Agents typically communicate with other agents in an attempt to accomplish a goal. R. Smith introduced a mechanism for collaboration between agents, known as the “contract net” protocol, in 1980. The mechanism is described in “The contract net protocol: High-level communication and control in distributed problem solver,” IEEE Transactions on Computers, 29(12):1104-1113, December 1980. When an agent needs the services of other agents, it plays the role of a “manager” and attempts to contract work out to other “contractor” agents. Other protocols apart from the “contract net” can be used, for example, “English Auction” and “Dutch Auction”. A library of these can be found at the FIPA web site identified by the identifiers XC00025 to XC00036. Alternativley, other forms of signals between agents could be used, for example, by updating a shared database record, or otherwise altering an object in the shared agent environment.
Many known agent-based systems employ the contract net protocol for allocating tasks to agents. In particular, the multi-agent system of Kwang Mong Sim etal, described in “Simulation of a multi-agent protocol for task allocation in cooperative design”, Proceedings of the IEEE systems, Man and cybernetics 1999, uses the contract net protocol to coordinate agent activities to accomplish a goal. Essentially, whenever an agent needs the services of another agent it announces the tasks to be done, whereupon at least some of the other agents bid for the tasks. The bid includes information such as expertise to perform the task and experience in performing similar tasks; the requesting agent selects a bidding agent in dependence on the information in the bid. In this system each agent is assumed to be responsible only for its own activities, so that a bid comprises information relating to a single agent, and the requesting agent is essentially comparing the capabilities of single agents.
International patent application GB98/02944 (publication number WO 99/17194) describes a resource handling system where, again, tasks are announced by an agent (referred to as manager), and so-called contracting agents evaluate the task with respect to their own abilities and commitments and submit bids (or not, as the case may be) in accordance therewith. The communication of task announcement, bid submission and acceptance is handled in accordance with the contract net protocol (and other similar communication protocols). In this system the contracting agents represent a work-processing centre, and, when formulating a bid, a contracting agent reviews availability, skills and rates of pay of the workforce associated with its respective work-processing centre. In this application the “workforce” is modelled as a single entity.
The Zeus Toolkit (“The Zeus Toolkit”, Collis, J, Ndumu, D, Nwana,H; BT Technology Journal 16(3) July 1998 p60-68) contains tools to construct agent systems that utilize the contract net protocol in this way. The article “Co-ordination in Software Agent Systems” (Nwana,H, Lee,L., & Jennings,J. BT Technology Journal 14(4) 1996) surveys these and other co-ordination systems.
The agent system described in “A hybrid agent-oriented infrastructure for modelling manufacturing enterprises”, Shen and Norrie, presented at the 11th workshop on knowledge acquisition, modelling and management, describes use of mediator agents in an agent-based multi-functional system. The mediator agents provide a “gateway” to other agent types, meaning that each agent subsystem is connected to the overall system through a special mediator. The authors consider this architecture to provide an efficient way of integrating a range of agent-based services. A mediator agent receives task requests from other mediator agents, then formulates and sends out task messages to agents associated therewith. Agents receiving the task messages formulate and return bids to their associated mediator agent, which passes the bid information to the originally requesting mediator agent.
In these known systems, each agent represents a single entity whose characteristics and capabilities are modelled by the agents; for example in the case of an agent representing a resource, each agent holds data representative of skills and location attributes corresponding to the resource, and negotiates for work on the basis of the attribute data.
In certain situations it would be useful if an agent could represent a group of entities, for example a team of workers. This would be useful because service-based industries are now considering allocating work to self-managed teams, rather than to individual workers. In self-managed teams, work is allocated to a team (typically by bidding, based on, e.g. the contract net protocol described above) and the team then has a responsibility to get the work done; if the work is not done, the team does not get paid. Typically the teams are flexible, meaning that workers can leave and join a team, effectively choosing the team that they want to be a part of (on the basis of incentives, personal constraints etc.).
However, such an arrangement is non-trivial to model. Currently a resource allocation system negotiates for resources with the assumption that the resources represented by an agent will be available. If the resources change, for example because a worker has moved from one team to another, this could mean that whichever job(s) involved that worker can no longer be carried out. As a result the system may have to repeat the negotiation process in respect of that/those jobs, and the team concerned will not receive payment.